//设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角
//移动到右下角的路径。 
//
// 
//
// 网格中的障碍物和空位置分别用 1 和 0 来表示。 
//
// 返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。 
//
// 示例 1： 
//
// 
//输入：[[0,0,0],[0,1,0],[0,0,0]]
//输出：[[0,0],[0,1],[0,2],[1,2],[2,2]]
//解释：
//输入中标粗的位置即为输出表示的路径，即
//0 行 0 列（左上角） -> 0 行 1 列 -> 0 行 2 列 -> 1 行 2 列 -> 2 行 2 列（右下角） 
//
// 说明：r 和 c 的值均不超过 100。 
//
// Related Topics 数组 动态规划 回溯 矩阵 👍 129 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-07-17 00:10:34
 * @description 面试题 08.02.迷路的机器人
 */
public class RobotInAGridLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 RobotInAGridLcci fun=new RobotInAGridLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	List<List<Integer>> res=new ArrayList<>();
	public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        dfs(new ArrayList<>(), 0, 0, obstacleGrid);
		return res;
    }
	private void  dfs(List<List<Integer>> path,int i,int j,int [][] grid){
		// 终止条件
		if (!res.isEmpty() ||i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 1) {
			return;
		}
		// 如果到达右下角
		if (i == grid.length - 1 && j == grid[0].length - 1) {
			path.add(List.of(i, j));
			res= new ArrayList<>(path);
			return;
		}

		// 标记当前位置为障碍物
		grid[i][j] = 1;
		path.add(List.of(i, j));

		// 向下移动
		dfs(path, i + 1, j, grid);
		// 向右移动
		dfs(path, i, j + 1, grid);
		path.remove(path.size() - 1); // 回溯
		// 不需要标记当前位置为障碍物，因为如果通过其他路径到达该位置，且无法到达终点，那就没必要再走一次
		//grid[i][j] =0;

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
